package com.mlamp.链表;

import com.mlamp.排序算法.基础排序;

public class 链表带环 {

    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);

    }


    /**
     * purely detect whether there is a cycle in lnode list
     *
     * @param head
     * @return
     */
    public static boolean havingCircle(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }


    /**
     * 判断链表带环
     *
     * @param head
     * @return
     */

    public static boolean existCircle(LNode head) {
        LNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }


    //检测链表是否带环
    public static boolean havingCircleA(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) return true;
        }
        return false;
    }


    public static boolean circleExist(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }


    public static boolean havingCircle3(LNode head) {
        LNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }

    public static LNode havingCircle4(LNode head) {
        LNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    //相交的位置
    public static LNode locCircleEnter(LNode head) {
        LNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    public static boolean havingCircle1(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) return true;
        }
        return false;
    }


    /**
     * purely detect whether there is a cycle in lnode list
     *
     * @param head
     * @return
     */
    public static LNode havingCircle2(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    public static LNode havingCircle33(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == head) break;
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != head) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    public static LNode havingCirCle3(LNode head) {
        LNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}
